ARC093F Dark Horse

Description

Link\text{Link}

Solution

西哥挖坟挖出来一道神仙题。

考虑问题本质:给定集合 A\mathcal{A} ,和 nn 个集合 Q1={2},Q2={3,4},\mathcal{Q_1}=\{2\},\mathcal{Q_2}=\{3,4\},\cdots ,要求构造排列 P\mathcal{P} ,满足 i[1,n]\forall i\in [1,n] ,将 Qi\mathcal{Q}_i 集合中的数视作下标时,对应的 Pj\mathcal{P}_j 的最小值均不在 A\mathcal{A} 中。

考虑容斥,每次钦定一个 S={Q1,Q2,}\mathcal{S}=\{\mathcal{Q}_1,\mathcal{Q}_2,\cdots\} 的子集 T\mathcal{T} 不满足要求,并求出方案数。但是

fi,sf_{i,s} 表示